package org.example.algorithm.array;

import java.util.*;

public class Test {

    /**
     * 力扣88:
     * 合并两个有序数组
     * 思路：
     * 双指针，比较当前数组值的大小
     *
     * @param
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int size = m + n;
        int[] arr = new int[size];
        int i = 0, x = 0, y = 0;
        while (x < m && y < n) {
            if (nums1[x] > nums2[y]) {
                arr[i++] = nums2[y++];
            } else {
                arr[i++] = nums1[x++];
            }
        }
        while (x < m) {
            arr[i++] = nums1[x++];
        }
        while (y < n) {
            arr[i++] = nums2[y++];
        }
        for (int index = 0; index < i; index++) {
            nums1[index] = arr[index];
        }
        arr = null;
    }

    public static void main(String[] args) {

    }

    /**
     * 力扣27.移除元素
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     * <p>
     * 思路：
     * 双指针，left，right，前后遍历，遇到对应的数，就将数组尾的元素赋值给左边数组的，只有当前元素不是对应要移除的元素，左指针往前
     */
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            if (nums[left] == val) {
                nums[left] = nums[right];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }

    /**
     * 力扣：26.删除有序数组的重复项
     * 描述：给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
     * 元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
     * 返回 k 。
     * <p>
     * 思路：
     * 双指针，一个指针停留在原地，另外一个指针向后遍历,
     * 如果当前左指针的前一个数等于nums[i],
     * 则将nums[i]赋值给对应的nums[left],
     * left不断向前
     * 1 2 2 3 3 4 5 7
     * 第一轮，left和i都+1，此时，left = 2， i = 2，此时两数相等，什么都不做，i继续往后移动，
     * i = 3，此时 nums[i] = 3, nums[left] = 2这时候 索引下标为2的被更新为 3.
     */
    public int removeDuplicates(int[] nums) {
        int left = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[left - 1] != nums[i]) {
                nums[left] = nums[i];
                left++;
            }
        }
        return left;
    }

    /**
     * 力扣：80. 删除有序数组中的重复项 II
     * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     * 与上述题目类似，不过移动的距离要变成2.
     *
     * @param nums
     * @return
     */
    public int removeDuplicates2(int[] nums) {
        int left = 2;
        int right = 2;
        while (right < nums.length) {
            if (nums[left - 2] != nums[right]) {
                nums[left] = nums[right];
                left++;
            }
            right++;
        }
        return left;
    }

    /**
     * leetcode：169多数元素
     * 描述：
     * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     * 思路：hash计数，排序返回n/2，bm投票（不太会），随机数学期望
     */
    public int majorityElement(int[] nums) {
         //1.hash表计数
//        Map<Integer, Integer> map = new HashMap<>();
//        for(int num : nums){
//            int t = map.getOrDefault(num, 0) + 1;
//            if(t > nums.length / 2){
//                return num;
//            }
//            map.put(num, t);
//        }
//        return -1;
        //2.排序，取n/2
//        Arrays.sort(nums);
//        return nums[nums.length / 2];
        //3.随机化
        Random random = new Random();
        while(true){
            int index = random.nextInt(nums.length);
            if(countOccurences(nums, nums[index]) > nums.length / 2){
                return nums[index];
            }
        }
    }

    private int countOccurences(int[] nums, int num) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    /**
     * 力扣189.轮转数组。
     * 描述：
     * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
     * 思路：
     * 1.新数组位移
     * 2.三次交换
     */
    public void rotate(int[] nums, int k) {
        //1.新数组位移
//        k %= nums.length;
//        int[] arr = new int[nums.length];
//        for(int i = 0; i < nums.length; i++){
//            arr[(i + k) % nums.length] = nums[i];
//        }
//        for(int i = 0; i < nums.length; i++){
//            nums[i] = arr[i];
//        }
//        arr = null;
        //2.三次交换
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    private void reverse(int[] arr, int start, int end){
        while(start <= end){
            swap(arr, start, end);
            start++;
            end--;
        }
    }

    private void swap(int[] arr, int i, int j){
        if(i != j){
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }
    }

    /**
     * 121.买卖股票的最佳时机。
     * 描述：
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     *
     * 思路：动态规划思想。
     */
    public int maxProfit(int[] prices) {
        int buy = -prices[0];
        int sell = 0;
        for(int i = 1; i < prices.length; i++){
            buy = Math.max(buy, -prices[i]);
            sell = Math.max(sell, buy + prices[i]);
        }
        return sell;
    }

    /**
     * 122. 买卖股票的最佳时机 II
     * 描述：
     * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
     * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。
     * 你也可以先购买，然后在 同一天 出售。
     * 返回 你能获得的 最大 利润 。
     *
     * 思路：动态规划。
     *
     */
    public int maxProfit2(int[] prices) {
        int sell = 0;
        int buy = -prices[0];
        for(int i = 0; i < prices.length; i++){
            buy = Math.max(buy, sell - prices[i]);
            sell = Math.max(sell, buy + prices[i]);
        }
        return sell;
    }

    /**
     * 123. 买卖股票的最佳时机 III
     * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     * 121 和 122的结合
     * 思路：动态规划。
     */
    public int maxProfit3(int[] prices) {
        int n = prices.length;
        int[] firstBuy = new int[n], firstSell = new int[n], secondBuy = new int[n], secondSell =new int[n];
        firstBuy[0] = -prices[0];
        firstSell[0] = 0;
        secondBuy[0] = -prices[0];
        secondSell[0] = 0;
        for(int i = 1; i < prices.length; i++){
            firstBuy[i] = Math.max(firstBuy[i - 1], -prices[i]);
            firstSell[i] = Math.max(firstSell[i - 1], firstBuy[i - 1] + prices[i]);
            secondBuy[i] = Math.max(secondBuy[i - 1], firstSell[i - 1] - prices[i]);
            secondSell[i] = Math.max(secondSell[i - 1], secondBuy[i - 1] + prices[i]);
        }
        return secondSell[n - 1];
    }

    /**
     * 力扣188.买卖股票的最佳时机 IV
     * 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     * 思路：
     * 动态规划。
     *
     * 第i天进入状态转移方程时，dp[i][j]有最大利润
     * 我们观察到，在第i天：当状态标识为偶数时，是买入且持有股票的状态，状态由两种情况转来，
     * 一是i - 1天就处于此状态，
     * 二是第i - 1天处于第j - 1次的 买入且不持有股票(已经卖出)的状态，第i天进行买入操作，有状态转移方程
     * dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - 1] - prices[i])
     * 当状态标识为奇数时，是买入且不持有股票(已经卖出)的状态，状态由两种情况转来，
     * 一是i - 1天就处于此状态，
     * 二是第i - 1天处于第j - 1次的 买入且持有股票的状态，第i天进行卖出操作，有状态转移方程
     * dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i])
     */
    public int maxProfit(int[] prices, int k) {
        int n = prices.length;
        int[][] dp = new int[n][2 * k];
        for(int i = 0; i < k; i++){
            dp[0][2 * i] = -prices[0];
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j < 2 * k; j++){
                if(j == 0) dp[i][j] = Math.max(dp[i - 1][j], -prices[i]);
                else if (j % 2 == 0) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
            }
        }
        return dp[n - 1][2 * k - 1];
    }

    /**
     * 力扣55.跳跃游戏。
     * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
     *
     * 思路：就直接遍历开始跳吧！
     */
    public boolean canJump(int[] nums) {
        int max = 0;
        for(int i = 0; i < nums.length; i++){
            if(max >= i){
                max = Math.max(max, i + nums[i]);
            }else{
                return false;
            }
        }
        return true;
    }

    /**
     * 力扣：45. 跳跃游戏 II
     * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
     * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
     * 0 <= j <= nums[i]
     * i + j < n
     * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
     *
     * 思路：遍历，就开始跳吧！
     */
    public int jump2(int[] nums) {
        int n = nums.length;
        int max = 0;
        int endMax = 0;
        int count = 0;
        for(int i = 0; i < n - 1 ; i++){
            max = Math.max(max, i + nums[i]);
            if(endMax == i){
                endMax = Math.max(endMax, max);
                count++;
            }
        }
        return count;
    }

    /**
     * 力扣274:H指数
     * 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
     * 根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，
     * 并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。
     * 思路：
     * 排序后，能找到
     * 我们找到了一篇被引用了至少 h+1次的论文
     */
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0;
        for(int i = citations.length - 1; i >= 0; i--){
            if(citations[i] > h){
                h++;
            }else{
                break;
            }
        }
        return h;
    }

    /**
     * 力扣238:除自身之外的数组乘积
     * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
     * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
     * 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
     *
     * 思路：双指针，前后遍历
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n];
        Arrays.fill(arr, 1);
        int beforeSum = 1, afterSum = 1;
        for(int i = 0, j = n -1;i < n; i++, j--){
            arr[i] *= beforeSum;
            arr[j] *= afterSum;
            beforeSum *= nums[i];
            afterSum *= nums[j];
        }
        return arr;
    }

    /**
     * 力扣134. 加油站
     * 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
     * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
     * 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
     *
     * 思路：贪心算法,找到差值最大的一个，
     * 如果当前 sum总和小于0，说明怎么样都走不了，如果>0,那么就是下一个。
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int sum = 0;
        int minIndex = -1;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < n;i++){
            sum += gas[i] - cost[i];
            if(sum < min && sum < 0){
                min = Math.min(min, sum);
                minIndex = i;
            }
        }
        return sum < 0 ? -1 : (minIndex + 1) % n;
    }

    /**
     * 力扣135.分发糖果
     * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
     * 你需要按照以下要求，给这些孩子分发糖果：
     * 每个孩子至少分配到 1 个糖果。
     * 相邻两个孩子评分更高的孩子会获得更多的糖果。
     * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
     * 思路：
     * 两次遍历：
     * 左规则：当 ratings[i−1]<ratings[i]时，i 号学生的糖果数量将比 i−1号孩子的糖果数量多。
     * 右规则：当 ratings[i]>ratings[i+1]时，i 号学生的糖果数量将比 i+1号孩子的糖果数量多。
     */
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        for(int i = 0; i < n; i++){
            if(i > 0 && ratings[i - 1] < ratings[i]){
                left[i] = left[i - 1] + 1;
            }else{
                left[i] = 1;
            }
        }
        int sum = 0, right = 0;
        for(int j = n - 1; j >=0; j--){
            if(j < n - 1 && ratings[j + 1] < ratings[j]){
                right++;
            }else{
                right = 1;
            }
            //符合两个规则的最大值。
            sum += Math.max(right, left[j]);
        }
        return sum;
    }

    /**
     * leetcode：42.接雨水
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * 重点题：理解两种解法
     */
    //1.解法1.按列来计算水
    public int trap(int[] height) {
        //记录水量的变量
        int sum = 0;
        //记录height的长度
        int n = height.length;
        for(int i = 1; i < n - 1;i++){
            int maxLeft = 0, maxRight = 0;
            for(int j = 0; j < i; j++){
                maxLeft = Math.max(maxLeft, height[j]);
            }
            for(int j = i + 1; j < n; j++){
                maxRight = Math.max(maxRight, height[j]);
            }
            int min = Math.min(maxLeft, maxRight);
            if(min - height[i] > 0){
                sum += min - height[i];
            }
        }
        return sum;
    }

    //2.解法2.动态规划.其实是按列求的一种变种.该方法还可以优化空间。
    public int trap2(int[] height){
        int sum = 0;
        int n = height.length;
        int[] maxLeft = new int[n];
        int[] maxRight = new int[n];
        for (int i = 1, j = n - 2; i < n - 1; i++, j--) {
            //这里要对应 + 1，或者 - 1是因为，要找到左边区间的/右边区间的
            maxLeft[i] = Math.max(maxLeft[i - 1], height[i - 1]);
            maxRight[j] = Math.max(maxRight[j + 1], height[j + 1]);
        }
        for(int i = 1; i < n - 1; i++){
            int min = Math.min(maxLeft[i], maxRight[i]);
            if(min > height[i]){
                sum += min - height[i];
            }
        }
        return sum;
    }

    /**
     * 13. 罗马数字转整数
     * 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     * 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
     * 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
     * I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
     * X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
     * C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
     * 给定一个罗马数字，将其转换成整数。
     *
     * 思路：hash表映射.遍历每一个字符，如果发现后一个字符大于现在这个字符，则说明当前字符应该反转符号
     */
    public int romanToInt(String str) {
        Map<Character, Integer> map = new HashMap<>(7);
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int sum = 0;
        int prev = map.get(str.charAt(0));
        for(int i = 1; i < str.length(); i++){
            int now = map.get(str.charAt(i));
            if(now > prev){
                prev = -prev;
            }
            sum += prev;
            prev = now;
        }
        sum += prev;
        return sum;
    }

    /**
     * 12.整数转罗马数字.
     * 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     * 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
     * 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。
     * 数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
     * I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
     * X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
     * C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
     * 给你一个整数，将其转为罗马数字。
     *
     * 思路：hash枚举，贪心算法.
     */
    public String intToRoman(int num) {
        Map<Integer, String> map = new LinkedHashMap<>();
        map.put(1000, "M");
        map.put(900, "CM");
        map.put(500, "D");
        map.put(400, "CD");
        map.put(100, "C");
        map.put(90, "XC");
        map.put(50, "L");
        map.put(40, "XL");
        map.put(10,"X");
        map.put(9, "IX");
        map.put(5, "V");
        map.put(4, "IV");
        map.put(1, "I");
        Set<Integer> integers = map.keySet();
        StringBuilder sb = new StringBuilder();
        for(Integer number : integers){
            while(num >= number){
                num -= number;
                sb.append(map.get(number));
            }
            if(num == 0){
                break;
            }
        }
        return sb.toString();
    }

    /**
     * 58. 最后一个单词的长度
     * 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
     * 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
     * 思路：反向遍历。
     */
    public int lengthOfLastWord(String s) {
        int i = s.length() - 1;
        while(s.charAt(i) == ' '){
            i--;
        }
        int count = 0;
        for(;i >= 0;i--){
            if(s.charAt(i) == ' '){
                break;
            }
            count++;
        }
        return count;
    }

    /**
     * 14. 最长公共前缀
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * 如果不存在公共前缀，返回空字符串 ""。
     * 思路：纵向扫描就行了
     */
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length <= 0) return "";
        int minLength = Integer.MAX_VALUE;
        for(String str : strs){
            minLength = Math.min(str.length(), minLength);
        }
        StringBuilder sb = new StringBuilder();
        out:for(int i = 0; i < minLength; i++){
            char c = strs[0].charAt(i);
            for(int j = 1; j < strs.length; j++){
                if(strs[j].charAt(i) != c){
                    break out;
                }
            }
            sb.append(c);
        }
        return sb.toString();
    }

    /**
     * 151. 反转字符串中的单词
     * 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
     * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
     * 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
     * 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
     *
     *  思路：栈
     */
    public String reverseWords(String s) {
        if(s == null || s.length() == 0) return "";
        Deque<String> stack = new LinkedList<>();
        s = s.trim();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            if(!sb.toString().equals("") && s.charAt(i) == ' '){
                stack.offerFirst(sb.toString());
                sb = new StringBuilder();
                continue;
            }
            if(s.charAt(i) != ' '){
                sb.append(s.charAt(i));
            }
        }
        while(!stack.isEmpty()){
            sb.append(' ');
            sb.append(stack.pollFirst());
        }
        return sb.toString();
    }

    /**
     * 力扣6.N字形变换.描述：
     * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
     * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
     * P   A   H   N
     * A P L S I I G
     * Y   I   R
     * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
     * 请你实现这个将字符串进行指定行数变换的函数：
     * string convert(string s, int numRows);
     *
     * 思路：
     * 0.首先进行临界判断,如果numsRows < 2，将s直接返回 （原因是 1行）；
     * 1.因为要按 numRows 去 打印，那么就要有 n行字符串
     * 2.定义两个变量，第一个变量用来定义当前的字符串索引。第二个用来定义字符指针的。
     * 3.到行数的行首，行底，索引反转。
     * 4.将对应的list，依次加上对应的字符串。
     * 5.返回结果。
     */
    public String convert(String s, int numRows) {
        if(numRows < 2) return s;
        List<StringBuilder> list = new ArrayList<>(numRows);
        for(int i = 0; i < numRows; i++) list.add(new StringBuilder());
        int index = 0, flag = -1;
        for(int i = 0; i < s.length(); i++){
            list.get(index).append(s.charAt(i));
            if(index == 0 || index == numRows - 1) flag = - flag;
            index += flag;
        }
        StringBuilder sb = new StringBuilder();
        for(StringBuilder item : list) sb.append(item.toString());
        return sb.toString();
    }

    /**
     * 力扣28.找出字符串中第一个匹配项的下标
     * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
     * 如果 needle 不是 haystack 的一部分，则返回  -1 。
     * 思路：
     * 1.暴力解法。
     *
     * 2.KMP解法
     * 3.String.indexOf() 就是暴力匹配算法
     */
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    /**
     *
     */
    public int strStr1(String haystack, String needle) {
        int m = haystack.length(), n = needle.length();
        for(int i = 0; i + n <= m; i++){
            boolean flag = true;
            for(int j = 0; j < n; j++){
                if(haystack.charAt(i + j) != needle.charAt(j)){
                    flag = false;
                    break;
                }
            }
            if(flag){
                return i;
            }
        }
        return -1;
    }

    /**
     * kmp算法
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr2(String haystack, String needle) {
        if (needle.isEmpty()) return 0;
        // 分别读取原串和匹配串的长度
        int n = haystack.length(), m = needle.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        haystack = " " + haystack;
        needle = " " + needle;
        char[] s = haystack.toCharArray();
        char[] p = needle.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m + 1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }
        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m;
        }
        return -1;
    }

    /**
     * 力扣68.文本左右对齐
     * 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
     * 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，
     * 使得每行恰好有 maxWidth 个字符。
     * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
     * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
     * 注意:
     * 单词是指由非空格字符组成的字符序列。
     * 每个单词的长度大于 0，小于等于 maxWidth。
     * 输入单词数组 words 至少包含一个单词。
     *
     * 思路：贪心算法。
     * 根据题干描述的贪心算法，对于每一行，我们首先确定最多可以放置多少单词，这样可以得到该行的空格个数，从而确定该行单词之间的空格个数。
     * 根据题目中填充空格的细节，我们分以下三种情况讨论。
     * 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格；
     * 当前行不是最后一行，且只有一个单词：该单词左对齐，在行末填充空格；
     * 当前行不是最后一行，且不只一个单词：设当前行单词数为 numWords\textit{numWords}numWords，空格数为 numSpaces
     * 我们需要将空格均匀分配在单词之间，则单词之间应至少有 avgSpaces= numWords−1/numSpaces个空格，对于多出来的
     * extraSpaces=numSpaces mod (numWords−1)个空格，应填在前 extraSpaces 个单词之间。
     * 因此，前 extraSpaces 个单词之间填充 avgSpaces+1 个空格，
     * 其余单词之间填充 avgSpaces个空格。
     */
    public List<String> fullJustify(String[] words, int maxWidth) {
        //0.先构造返回参数.
        List<String> data = new ArrayList<>();
        int right = 0, n = words.length;
        while(true){
            int left = right;
            int sumLength = 0;
            while(right < n && sumLength + words[right].length() + right - left <= maxWidth){
                sumLength += words[right++].length();
            }
            if(right == n){
                StringBuilder sb = makeStringBuilder(words, left, right, " ");
                sb.append(makeBlank(maxWidth - sb.length()));
                data.add(sb.toString());
                return data;
            }
            int numWords = right - left;
            int numLength = maxWidth - sumLength;
            if(numWords == 1){
                StringBuilder sb = new StringBuilder(words[left]);
                sb.append(makeBlank(numLength));
                data.add(sb.toString());
                continue;
            }
            int avgSpaces = numLength / (numWords - 1);
            int extraSpaces = numLength % (numWords - 1);
            StringBuilder sb = makeStringBuilder(words, left, left + extraSpaces + 1, makeBlank(avgSpaces));
            sb.append(makeBlank(avgSpaces));
            sb.append(makeStringBuilder(words, left + extraSpaces + 1, right, makeBlank(avgSpaces)));
            data.add(sb.toString());
        }
    }

    private String makeBlank(int n) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++)sb.append(' ');
        return sb.toString();
    }

    private StringBuilder makeStringBuilder(String[] words, int left, int right, String space) {
        StringBuilder sb = new StringBuilder(words[left]);
        for(int i = left + 1; i < right; i++){
            sb.append(space);
            sb.append(words[i]);
        }
        return sb;
    }
}
